{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost to Cut a Stick"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #切棍子的最小成本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一根长度为 <code>n</code> 个单位的木棍，棍上从 <code>0</code> 到 <code>n</code> 标记了若干位置。例如，长度为 <strong>6</strong> 的棍子可以标记如下：</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/09/statement.jpg\" style=\"height: 111px; width: 521px;\" /></p>\n",
    "\n",
    "<p>给你一个整数数组 <code>cuts</code> ，其中 <code>cuts[i]</code> 表示你需要将棍子切开的位置。</p>\n",
    "\n",
    "<p>你可以按顺序完成切割，也可以根据需要更改切割的顺序。</p>\n",
    "\n",
    "<p>每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。</p>\n",
    "\n",
    "<p>返回切棍子的 <strong>最小总成本</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/09/e1.jpg\" style=\"height: 284px; width: 350px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, cuts = [1,3,4,5]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>按 [1, 3, 4, 5] 的顺序切割的情况如下所示：\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/09/e11.jpg\" style=\"height: 284px; width: 350px;\" />\n",
    "第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。\n",
    "而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 9, cuts = [5,6,1,4,2]\n",
    "<strong>输出：</strong>22\n",
    "<strong>解释：</strong>如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 10^6</code></li>\n",
    "\t<li><code>1 <= cuts.length <= min(n - 1, 100)</code></li>\n",
    "\t<li><code>1 <= cuts[i] <= n - 1</code></li>\n",
    "\t<li><code>cuts</code> 数组中的所有整数都 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-to-cut-a-stick](https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-to-cut-a-stick](https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[1,3,4,5]', '9\\n[5,6,1,4,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x, y = startPos\n",
    "        X, Y = homePos\n",
    "        ans = sum(rowCosts[x+1:X+1]) if x < X else sum(rowCosts[X:x])\n",
    "        ans += sum(colCosts[y+1:Y+1]) if y < Y else sum(colCosts[Y:y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        m = len(rowCosts)\n",
    "        n = len(colCosts)\n",
    "        sx,sy = startPos\n",
    "        tx,ty = homePos\n",
    "        if sx==tx and sy==ty:\n",
    "            return 0\n",
    "        smallx = sx if sx<tx else tx\n",
    "        largex = tx if sx<tx else sx\n",
    "        smally = sy if sy<ty else ty\n",
    "        largey = ty if sy<ty else sy\n",
    "        res = 0\n",
    "        if largex!=smallx:\n",
    "            for i in range(smallx+1, largex):\n",
    "                res += rowCosts[i]\n",
    "            res += rowCosts[tx]\n",
    "        if largey!=smally:\n",
    "            for i in range(smally+1, largey):\n",
    "                res += colCosts[i]\n",
    "            res += colCosts[ty]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minCost(self, startPos, homePos, rowCosts, colCosts):\n",
    "        return (sum(rowCosts[startPos[0] + 1 : homePos[0] + 1]) if startPos[0] < homePos[0] else sum(rowCosts[homePos[0] : startPos[0]]) if startPos[0] > homePos[0] else 0) \\\n",
    "             + (sum(colCosts[startPos[1] + 1 : homePos[1] + 1]) if startPos[1] < homePos[1] else sum(colCosts[homePos[1] : startPos[1]]) if startPos[1] > homePos[1] else 0)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "\n",
    "        \n",
    "        \n",
    "        minx, maxx = min(startPos[0], homePos[0]), max(startPos[0], homePos[0])\n",
    "        miny, maxy = min(startPos[1], homePos[1]), max(startPos[1], homePos[1])\n",
    "        ret = sum(rowCosts[i] for i in range(minx, maxx + 1)) + sum(colCosts[i] for i in range(miny, maxy + 1))\n",
    "        return ret - rowCosts[startPos[0]] - colCosts[startPos[1]]\n",
    "        \n",
    "        \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        if(startPos[0] > homePos[0]):\n",
    "            result += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        else:\n",
    "            result += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "        if(startPos[1] > homePos[1]):\n",
    "            result += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        else:\n",
    "            result += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in self.getSteps(startPos[0], homePos[0]):\n",
    "            result += rowCosts[i]\n",
    "        for i in self.getSteps(startPos[1], homePos[1]):\n",
    "            result += colCosts[i]\n",
    "        return result\n",
    "\n",
    "    def getSteps(self, startPos: int, endPos: int):\n",
    "        step = 1 if startPos <= endPos else -1\n",
    "        return range(startPos + step, endPos + step, step)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        if(startPos[0] > homePos[0]):\n",
    "            result += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        else:\n",
    "            result += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "        if(startPos[1] > homePos[1]):\n",
    "            result += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        else:\n",
    "            result += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        res = 0\n",
    "        if startPos[0] < homePos[0]:res += sum(rowCosts[startPos[0] + 1:homePos[0] + 1])\n",
    "        else: res += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        if startPos[1] < homePos[1]:res += sum(colCosts[startPos[1] + 1:homePos[1] + 1])\n",
    "        else: res += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        \n",
    "        return  res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x0, y0 = startPos\n",
    "        x1, y1= homePos\n",
    "        ans = -rowCosts[x0] - colCosts[y0]\n",
    "        if x0 > x1:\n",
    "            x0, x1 = x1, x0\n",
    "        if y0 > y1:\n",
    "            y0, y1 = y1, y0\n",
    "        for cost in rowCosts[x0:x1+1]:\n",
    "            ans += cost\n",
    "        for cost in colCosts[y0:y1+1]:\n",
    "            ans += cost\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        if(startPos[0] > homePos[0]):\n",
    "            result += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        else:\n",
    "            result += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "        if(startPos[1] > homePos[1]):\n",
    "            result += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        else:\n",
    "            result += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        return sum(rowCosts[x] for x in range(min(startPos[0], homePos[0]), max(startPos[0], homePos[0]) + 1)) \\\n",
    "         + sum(colCosts[x] for x in range(min(startPos[1], homePos[1]), max(startPos[1], homePos[1]) + 1)) \\\n",
    "         - rowCosts[startPos[0]] - colCosts[startPos[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x0, y0, x1, y1 = startPos[0], startPos[1], homePos[0], homePos[1]\n",
    "        ans = -rowCosts[x0] - colCosts[y0] # 初始的行列无需计算\n",
    "        if x0 > x1: \n",
    "            x0, x1 = x1, x0 # 交换位置，保证 x0 <= x1\n",
    "        if y0 > y1: \n",
    "            y0, y1 = y1, y0 # 交换位置，保证 y0 <= y1\n",
    "        for cost in rowCosts[x0 : x1+1]:\n",
    "            ans += cost # 统计答案\n",
    "        for cost in colCosts[y0 : y1+1]:\n",
    "            ans += cost # 统计答案\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if startPos[0] != homePos[0]:\n",
    "            if startPos[0] < homePos[0]:\n",
    "                ans += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "            else:\n",
    "                ans += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        if startPos[1] != homePos[1]:\n",
    "            if startPos[1] < homePos[1]:\n",
    "                ans += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "            else:\n",
    "                ans += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        si, sj = startPos\n",
    "        ei, ej = homePos\n",
    "        \n",
    "        si, ei = (si, ei) if si <= ei else (ei, si)\n",
    "        sj, ej = (sj, ej) if sj <= ej else (ej, sj)\n",
    "\n",
    "        return (\n",
    "            sum(rowCosts[si:ei + 1])\n",
    "            + sum(colCosts[sj:ej + 1])\n",
    "            - rowCosts[startPos[0]]\n",
    "            - colCosts[startPos[1]]\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        # 代价都是正的，所以不可绕路\n",
    "        # 贪心找x, y 较小分量即可\n",
    "        x1, y1, x2, y2 = startPos[0], startPos[1], homePos[0], homePos[1]\n",
    "\n",
    "        ans = -rowCosts[x1] - colCosts[y1]\n",
    "        # 水平移动代价\n",
    "        if x1 > x2:\n",
    "            x1, x2 = x2, x1\n",
    "        for i in range(x1, x2+1):\n",
    "            ans += rowCosts[i]\n",
    "        \n",
    "        # 垂直移动代价\n",
    "        if y1 > y2:\n",
    "            y1, y2 = y2, y1\n",
    "        for i in range(y1, y2+1):\n",
    "            ans += colCosts[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "\n",
    "        if homePos == startPos:\n",
    "            return 0\n",
    "\n",
    "        st = startPos[0]\n",
    "        flag = 1\n",
    "        if startPos[0] > homePos[0]:\n",
    "            flag = -1 \n",
    "        cst = 0\n",
    "        while st != homePos[0]:\n",
    "            st += flag\n",
    "            cst += rowCosts[st]\n",
    "\n",
    "        st = startPos[1]\n",
    "        flag = 1\n",
    "        if startPos[1] > homePos[1]:\n",
    "            flag = -1 \n",
    "\n",
    "        while st != homePos[1]:\n",
    "            st += flag\n",
    "            cst += colCosts[st]\n",
    "\n",
    "        return cst        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        rmin = min(startPos[0], homePos[0])\n",
    "        rmax = max(startPos[0], homePos[0])\n",
    "        cmin = min(startPos[1], homePos[1])\n",
    "        cmax = max(startPos[1], homePos[1])\n",
    "\n",
    "        ans = sum(rowCosts[rmin:rmax+1]) + sum(colCosts[cmin:cmax+1])\n",
    "        ans -= rowCosts[startPos[0]]\n",
    "        ans -= colCosts[startPos[1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x,y=startPos[0],startPos[1]\n",
    "        a,b=homePos[0],homePos[1]\n",
    "        ans=0\n",
    "        if x<a:\n",
    "            ans+=sum(rowCosts[x+1:a+1])\n",
    "        else:\n",
    "            ans+=sum(rowCosts[a:x])\n",
    "        if y<b:\n",
    "            ans+=sum(colCosts[y+1:b+1])\n",
    "        else:\n",
    "            ans+=sum(colCosts[b:y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        startRow, endRow = startPos[0], homePos[0]\n",
    "        startCol, endCol = startPos[1], homePos[1]\n",
    "        ans = 0\n",
    "        if startRow < endRow:\n",
    "            for i in range(startRow + 1, endRow + 1):\n",
    "                ans += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(startRow - 1, endRow - 1, -1):\n",
    "                ans += rowCosts[i]\n",
    "        if startCol < endCol:\n",
    "            for i in range(startCol + 1, endCol + 1):\n",
    "                ans += colCosts[i]\n",
    "        else:\n",
    "            for i in range(startCol - 1, endCol - 1, -1):\n",
    "                ans += colCosts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in self.getSteps(startPos[0], homePos[0]):\n",
    "            result += rowCosts[i]\n",
    "        for i in self.getSteps(startPos[1], homePos[1]):\n",
    "            result += colCosts[i]\n",
    "        return result\n",
    "\n",
    "    def getSteps(self, startPos: int, endPos: int):\n",
    "        step = 1 if startPos <= endPos else -1\n",
    "        return range(startPos + step, endPos + step, step)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(list(Solution().getSteps(5,2)))\n",
    "    print(Solution().minCost([5,5] ,[5,2] ,[7,1,3,3,5,3,22,10,23],[5,5,6,2,0,16]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans=0\n",
    "        step= -1 if startPos[0]>homePos[0] else 1\n",
    "        for i in range(startPos[0]+step, homePos[0]+step, step):\n",
    "            ans+=rowCosts[i]\n",
    "        step= -1 if startPos[1]>homePos[1] else 1\n",
    "        for i in range(startPos[1], homePos[1], step):\n",
    "            ans+=colCosts[i+step]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        sx, sy = startPos\n",
    "        hx, hy = homePos\n",
    "        \n",
    "        ans = 0\n",
    "        if sx <= hx:\n",
    "            ans += sum(rowCosts[i] for i in range(sx+1, hx+1))\n",
    "        else:\n",
    "            ans += sum(rowCosts[i] for i in range(hx, sx))\n",
    "        \n",
    "        if sy <= hy:\n",
    "            ans += sum(colCosts[i] for i in range(sy+1, hy+1))\n",
    "        else:\n",
    "            ans += sum(colCosts[i] for i in range(hy, sy))\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans=0\n",
    "        step= -1 if startPos[0]>homePos[0] else 1\n",
    "        for i in range(startPos[0], homePos[0], step):\n",
    "            ans+=rowCosts[i+step]\n",
    "        step= -1 if startPos[1]>homePos[1] else 1\n",
    "        for i in range(startPos[1], homePos[1], step):\n",
    "            ans+=colCosts[i+step]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        if startPos == homePos:\n",
    "            return 0\n",
    "\n",
    "\n",
    "        def hp(h, s, costs):\n",
    "            dx = h - s \n",
    "\n",
    "            ans = 0\n",
    "\n",
    "            if dx == 0:\n",
    "                pass\n",
    "            elif dx > 0:\n",
    "                for k in range(s + 1, h + 1):\n",
    "                    ans += costs[k]\n",
    "            else:\n",
    "                for k in range(h, s):\n",
    "                    ans += costs[k]\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        return hp(homePos[0], startPos[0], rowCosts) + hp(homePos[1], startPos[1], colCosts)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        dx, dy = 0, 0\n",
    "        if startPos[0] <= homePos[0]:\n",
    "            dx = 1\n",
    "        else:\n",
    "            dx = -1\n",
    "        \n",
    "        if startPos[1] <= homePos[1]:\n",
    "            dy = 1\n",
    "        else:\n",
    "            dy = -1\n",
    "        \n",
    "        return sum(rowCosts[i] for i in range(startPos[0] + dx, homePos[0] + dx, dx)) + sum(colCosts[i] for i in range(startPos[1] + dy, homePos[1] + dy, dy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans=0\n",
    "        step= -1 if startPos[0]>homePos[0] else 1\n",
    "        for i in range(startPos[0]+step, homePos[0]+step, step):\n",
    "            ans+=rowCosts[i]\n",
    "        step= -1 if startPos[1]>homePos[1] else 1\n",
    "        for i in range(startPos[1]+step, homePos[1]+step, step):\n",
    "            ans+=colCosts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        row_diff = homePos[0] - startPos[0]\n",
    "        col_diff = homePos[1] - startPos[1]\n",
    "        now_pos = startPos\n",
    "        cost = 0\n",
    "        while now_pos != homePos:\n",
    "            if row_diff > 0:\n",
    "                cost += rowCosts[now_pos[0] + 1]\n",
    "                now_pos[0] += 1\n",
    "                row_diff -= 1\n",
    "            elif row_diff < 0:\n",
    "                cost += rowCosts[now_pos[0] - 1]\n",
    "                now_pos[0] -= 1\n",
    "                row_diff += 1\n",
    "\n",
    "            if col_diff > 0:\n",
    "                cost += colCosts[now_pos[1] + 1]\n",
    "                now_pos[1] += 1\n",
    "                col_diff -= 1\n",
    "            elif col_diff < 0:\n",
    "                cost += colCosts[now_pos[1] - 1]\n",
    "                now_pos[1] -= 1\n",
    "                col_diff += 1\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: List[int], h: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        res = 0\n",
    "        if s[0] <= h[0]:\n",
    "            for i in range(min(s[0],h[0])+1,max(s[0],h[0])+1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(s[0]-1,h[0]-1,-1):\n",
    "                res += rowCosts[i]\n",
    "        if s[1] <= h[1]:\n",
    "            for i in range(min(s[1],h[1])+1,max(s[1],h[1])+1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(s[1]-1,h[1]-1,-1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        if startPos[0]>homePos[0]:\n",
    "            dx=-1\n",
    "        else:\n",
    "            dx=1\n",
    "        if startPos[1]>homePos[1]:\n",
    "            dy=-1\n",
    "        else:\n",
    "            dy=1\n",
    "        ans=0\n",
    "        for i in range(startPos[0]+dx, homePos[0]+dx, dx):\n",
    "            ans+=rowCosts[i]\n",
    "        for i in range(startPos[1]+dy, homePos[1]+dy, dy):\n",
    "            ans+=colCosts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: List[int], h: List[int], rs: List[int], cs: List[int]) -> int:\n",
    "        if s[0] == h[0] and s[1] == h[1]:\n",
    "            return 0\n",
    "        r, c = len(rs), len(cs)\n",
    "        \n",
    "        ans = 0\n",
    "        row_s, row_e = s[0], h[0]\n",
    "        if row_s >= row_e:\n",
    "            for i in range(row_s-1, row_e-1,-1):\n",
    "                ans += rs[i]\n",
    "        else:\n",
    "            for i in range(row_s+1, row_e+1):\n",
    "                ans += rs[i]\n",
    "\n",
    "        col_s, col_e = s[1], h[1]\n",
    "        if col_s >= col_e:\n",
    "            for i in range(col_s-1, col_e-1,-1):\n",
    "                ans += cs[i]\n",
    "        else:\n",
    "            for i in range(col_s+1, col_e+1):\n",
    "                ans += cs[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans1=0\n",
    "        ans2=0\n",
    "        if startPos==homePos:\n",
    "            return 0\n",
    "        while startPos[0]!=homePos[0]:\n",
    "            if startPos[0]>homePos[0]:\n",
    "                startPos[0]-=1\n",
    "                ans1+=rowCosts[startPos[0]]\n",
    "            if startPos[0]<homePos[0]:\n",
    "                startPos[0]+=1\n",
    "                ans1+=rowCosts[startPos[0]]\n",
    "        while startPos[1]!=homePos[1]:\n",
    "            if startPos[1]>homePos[1]:\n",
    "                startPos[1]-=1\n",
    "                ans2+=colCosts[startPos[1]]\n",
    "            if startPos[1]<homePos[1]:\n",
    "                startPos[1]+=1\n",
    "                ans2+=colCosts[startPos[1]]\n",
    "        return (ans1+ans2)\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "\n",
    "        x1, y1 = startPos\n",
    "        x2, y2 = homePos\n",
    "        res = 0\n",
    "        if x1 <= x2:\n",
    "            for i in range(x1+1, x2+1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(x2, x1):\n",
    "                res += rowCosts[i]\n",
    "        if y1 <= y2:\n",
    "            for j in range(y1+1, y2+1):\n",
    "                res += colCosts[j]\n",
    "        else:\n",
    "            for j in range(y2, y1):\n",
    "                res += colCosts[j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        row_delta = col_delta = 1\n",
    "        if startPos[0] > homePos[0]:\n",
    "            row_delta = -1\n",
    "        if startPos[1] > homePos[1]:\n",
    "            col_delta = -1\n",
    "        \n",
    "        res = 0\n",
    "        for index in range(startPos[0] + row_delta, homePos[0] + row_delta, row_delta):\n",
    "            res += rowCosts[index]\n",
    "        for index in range(startPos[1] + col_delta, homePos[1] + col_delta, col_delta):\n",
    "            res += colCosts[index]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minCost(self, startPos, homePos, rowCosts, colCosts):\n",
    "        return (sum(rowCosts[startPos[0] + 1 : homePos[0] + 1]) if startPos[0] < homePos[0] else sum(rowCosts[homePos[0] : startPos[0]]) if startPos[0] > homePos[0] else 0) \\\n",
    "             + (sum(colCosts[startPos[1] + 1 : homePos[1] + 1]) if startPos[1] < homePos[1] else sum(colCosts[homePos[1] : startPos[1]]) if startPos[1] > homePos[1] else 0)        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        # dfs(i,j)从i，j到达终点的最小代价\n",
    "        # 因为cost都是正数，如果又绕过来l肯定代价会更大\n",
    "        sx,sy,tx,ty=startPos[0],startPos[1],homePos[0],homePos[1]\n",
    "        res=0\n",
    "        if sx<tx:\n",
    "            for row in range(sx+1,tx+1):\n",
    "                res+=rowCosts[row]\n",
    "        elif sx>tx:\n",
    "            for row in range(sx-1,tx-1,-1):\n",
    "                res+=rowCosts[row]\n",
    "        if sy<ty:\n",
    "            for row in range(sy+1,ty+1):\n",
    "                res+=colCosts[row]\n",
    "        elif sy>ty:\n",
    "            for row in range(sy-1,ty-1,-1):\n",
    "                res+=colCosts[row]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        rs = 0\n",
    "        for i in range(min(startPos[0], homePos[0]), max(startPos[0], homePos[0])+1):\n",
    "            rs += rowCosts[i]\n",
    "        for j in range(min(startPos[1], homePos[1]), max(startPos[1], homePos[1])+1):\n",
    "            rs += colCosts[j]\n",
    "        return rs-colCosts[startPos[1]]-rowCosts[startPos[0]]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0  # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        y1, x1 = startPos\n",
    "        y2, x2 = homePos\n",
    "        if y1 <= y2:\n",
    "            dy = 1\n",
    "        else:\n",
    "            dy = -1\n",
    "        if x1 <= x2:\n",
    "            dx = 1\n",
    "        else:\n",
    "            dx = -1\n",
    "        ret = sum(rowCosts[y] for y in range(y1+dy, y2+dy, dy))\n",
    "        ret += sum(colCosts[x] for x in range(x1+dx, x2+dx, dx))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: list[int], target: list[int], specialRoads: list[list[int]]) -> int:\n",
    "        nodes = set([tuple(start), tuple(target)])\n",
    "        cost = collections.defaultdict(int)\n",
    "\n",
    "        for x1, y1, x2, y2, c in specialRoads:\n",
    "            if (x1, y1, x2, y2) not in cost:\n",
    "                cost[(x1, y1, x2, y2)] = c\n",
    "            else:\n",
    "                cost[(x1, y1, x2, y2)] = min(cost[(x1, y1, x2, y2)], c)\n",
    "            nodes.add((x1, y1))\n",
    "            nodes.add((x2, y2))\n",
    "\n",
    "        minHeap = [(0, start[0], start[1])]\n",
    "        visited = set()\n",
    "        minCost = {node: float('inf') for node in nodes}\n",
    "        minCost[(start[0], start[1])] = 0\n",
    "\n",
    "        while minHeap:\n",
    "            c, x, y = heapq.heappop(minHeap)\n",
    "            if (x, y) in visited:\n",
    "                continue\n",
    "            visited.add((x, y))\n",
    "\n",
    "            for nx, ny in nodes:\n",
    "                if (nx, ny) not in visited:\n",
    "                    sc = cost[(x, y, nx, ny)] if (x, y, nx, ny) in cost else float('inf')\n",
    "                    nc = min(sc, abs(nx-x)+abs(ny-y)) + c\n",
    "                    if nc < minCost[(nx, ny)]:\n",
    "                        minCost[(nx, ny)] = nc\n",
    "                        heapq.heappush(minHeap, (nc, nx, ny))\n",
    "\n",
    "        return minCost[(target[0], target[1])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        ans = [-1]*n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a,b,c in roads:\n",
    "            g[a-1].append((b-1, c))\n",
    "            g[b-1].append((a-1, c))\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            dist = [float('inf')]*n\n",
    "            dist[start] = 0\n",
    "            mheap = [(0,start)]\n",
    "            while mheap:\n",
    "                dis,x = heapq.heappop(mheap)\n",
    "                if dis>dist[x]:\n",
    "                    continue\n",
    "                for nextN,nextD in g[x]:\n",
    "                    if dis+nextD < dist[nextN]:\n",
    "                        dist[nextN] = dis+nextD\n",
    "                        heapq.heappush(mheap, (dist[nextN], nextN))\n",
    "                pass\n",
    "            \n",
    "            cur_min = float('inf')\n",
    "            for i in range(n):\n",
    "                cur = (k+1)*dist[i] + appleCost[i]\n",
    "                cur_min = min(cur_min, cur) \n",
    "            return cur_min\n",
    "\n",
    "        for i in range(n):\n",
    "            ans[i] = dijkstra(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        e=collections.defaultdict(list)\n",
    "        for a,b,c in roads:\n",
    "            e[a].append((b,c*k+c))\n",
    "            e[b].append((a,c*k+c))\n",
    "        def dijk(start):\n",
    "            q=[(0,start)]\n",
    "            ret=appleCost[start-1]\n",
    "            find=[False]*(n+1)\n",
    "            while q:\n",
    "                cost,tp=heapq.heappop(q)\n",
    "                ret=min(ret,cost+appleCost[tp-1])\n",
    "                if find[tp]:\n",
    "                    continue\n",
    "                find[tp]=True\n",
    "                for i,newcost in e[tp]:\n",
    "                    if find[i]:\n",
    "                        continue\n",
    "                    heapq.heappush(q,(cost+newcost,i))\n",
    "            return  ret \n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            ans[i]=dijk(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for a, b, c in roads:\n",
    "            g[a - 1].append((b - 1, c * (k + 1)))\n",
    "            g[b - 1].append((a - 1, c * (k + 1)))\n",
    "\n",
    "        visited = [0] * n\n",
    "        pq = sorted((c, i) for i, c in enumerate(appleCost))\n",
    "        while pq:\n",
    "            c, u = heapq.heappop(pq)\n",
    "            if visited[u]:\n",
    "                continue\n",
    "\n",
    "            visited[u] = 1\n",
    "            for v, nc in g[u]:\n",
    "                if appleCost[v] > c + nc:\n",
    "                    appleCost[v] = c + nc\n",
    "                    heapq.heappush(pq, (appleCost[v], v))\n",
    "\n",
    "        return appleCost\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from math import inf\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        adj = [[] for _ in range(n + 1)]\n",
    "        for u, v, cost in roads:\n",
    "            u -= 1\n",
    "            v -= 1\n",
    "            adj[u].append((v, (k + 1) * cost))\n",
    "            adj[v].append((u, (k + 1) * cost))\n",
    "        \n",
    "        # node n represents apple\n",
    "        for i, c in enumerate(appleCost):\n",
    "            adj[i].append((n, c))\n",
    "            adj[n].append((i, c))\n",
    "\n",
    "        # Dijkstra find shortest path from node n (apple) to every node\n",
    "        dist = [inf] * n + [0]\n",
    "        # heap stores (cost, node)\n",
    "        h = [(0, n)]\n",
    "        while h:\n",
    "            d, u = heappop(h)\n",
    "            if dist[u] < d:\n",
    "                continue\n",
    "            for v, w in adj[u]:\n",
    "                if dist[v] > d + w:\n",
    "                    dist[v] = d + w\n",
    "                    heappush(h, (d + w, v))\n",
    "            \n",
    "        return dist[:n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for a, b, c in roads:\n",
    "            g[a - 1].append((b - 1, c * (k + 1)))\n",
    "            g[b - 1].append((a - 1, c * (k + 1)))\n",
    "\n",
    "        visited = [0] * n\n",
    "        pq = sorted((c, i) for i, c in enumerate(appleCost))\n",
    "        while pq:\n",
    "            c, u = heapq.heappop(pq)\n",
    "            if visited[u]:\n",
    "                continue\n",
    "\n",
    "            visited[u] = 1\n",
    "            for v, nc in g[u]:\n",
    "                if appleCost[v] > c + nc:\n",
    "                    appleCost[v] = c + nc\n",
    "                    heapq.heappush(pq, (appleCost[v], v))\n",
    "\n",
    "        return appleCost\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        cost = appleCost[::]\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in roads:\n",
    "            x, y, z = u - 1, v - 1, (k + 1) * w\n",
    "            g[x].append((y, z))\n",
    "            g[y].append((x, z))\n",
    "        h = []\n",
    "        for i, x in enumerate(appleCost):\n",
    "            heappush(h, (x,i))\n",
    "        while h:\n",
    "            cost, x = heappop(h)\n",
    "            if cost > appleCost[x]: continue\n",
    "            for y, w in g[x]:\n",
    "                if cost + w < appleCost[y]:\n",
    "                    appleCost[y] = cost + w \n",
    "                    heappush(h, (appleCost[y], y))\n",
    "        return appleCost\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in roads:\n",
    "            g[a - 1].append([b - 1, cost])\n",
    "            g[b - 1].append([a - 1, cost])\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            ans = inf\n",
    "            dist = [inf] * n\n",
    "            dist[start] = 0\n",
    "            q = [(0, start)]\n",
    "            while q:\n",
    "                cost, node = heapq.heappop(q)\n",
    "                ans = min(ans, cost * (k + 1) + appleCost[node])\n",
    "                if dist[node] < cost:\n",
    "                    continue\n",
    "                for nei, cost in g[node]:\n",
    "                    d = dist[node] + cost\n",
    "                    if d < dist[nei]:\n",
    "                        dist[nei] = d\n",
    "                        heapq.heappush(q, (d, nei))\n",
    "            return ans\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in roads:\n",
    "            g[u - 1].append((v - 1, w))\n",
    "            g[v - 1].append((u - 1, w))\n",
    "        def dijkstra(i):\n",
    "            pq, visited, res = [(0, i)], set(), inf\n",
    "            while pq:\n",
    "                w, node = heappop(pq)\n",
    "                if node not in visited:\n",
    "                    visited.add(node)\n",
    "                    res = min(res, w + appleCost[node])\n",
    "                    for nei, weight in g[node]:\n",
    "                        heappush(pq, (w + weight * (k + 1), nei))\n",
    "            return res\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in roads:\n",
    "            g[a - 1].append([b - 1, cost])\n",
    "            g[b - 1].append([a - 1, cost])\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            res, dist = inf, [inf] * n\n",
    "            dist[start], q = 0, [(0, start)]\n",
    "            while q:\n",
    "                cost, node = heapq.heappop(q)\n",
    "                res = min(res, cost * (k + 1) + appleCost[node])\n",
    "                for nei, cost in g[node]:\n",
    "                    d = dist[node] + cost\n",
    "                    if d < dist[nei]:\n",
    "                        dist[nei] = d\n",
    "                        heapq.heappush(q, (d, nei))\n",
    "            return res\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        adj = [[] for _ in range(n + 1)]\n",
    "        for u, v, cost in roads:\n",
    "            u -= 1\n",
    "            v -= 1\n",
    "            adj[u].append((v, (k + 1) * cost))\n",
    "            adj[v].append((u, (k + 1) * cost))\n",
    "        \n",
    "        # node n represents apple\n",
    "        for i, c in enumerate(appleCost):\n",
    "            adj[i].append((n, c))\n",
    "            adj[n].append((i, c))\n",
    "\n",
    "        # Dijkstra find shortest path from node n (apple) to every node\n",
    "        dist = [inf] * n + [0]\n",
    "        # heap stores (cost, node)\n",
    "        h = [(0, n)]\n",
    "        while h:\n",
    "            d, u = heappop(h)\n",
    "            if dist[u] < d:\n",
    "                continue\n",
    "            for v, w in adj[u]:\n",
    "                if dist[v] > d + w:\n",
    "                    dist[v] = d + w\n",
    "                    heappush(h, (d + w, v))\n",
    "            \n",
    "        return dist[:n]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in roads:\n",
    "            g[a - 1].append([b - 1, cost])\n",
    "            g[b - 1].append([a - 1, cost])\n",
    "        \n",
    "        def dijkstra(start: int):\n",
    "            ans = float('inf')\n",
    "            dist = [float('inf')] * n\n",
    "            dist[start] = 0\n",
    "            q = [(0, start)]\n",
    "            while q:\n",
    "                cost, x = heapq.heappop(q)\n",
    "                ans = min(ans, cost * (k + 1) + appleCost[x])\n",
    "                if dist[x] < cost:\n",
    "                    continue\n",
    "                for y, cost in g[x]:\n",
    "                    d = dist[x] + cost\n",
    "                    if d < dist[y]:\n",
    "                        dist[y] = d\n",
    "                        heapq.heappush(q, (d, y))\n",
    "            return ans\n",
    "        \n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            ans[i] = dijkstra(i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        graph = [set() for i in range(n + 1)]\n",
    "        for i, j, w in roads:\n",
    "            graph[i].add((j, w * (k + 1)))\n",
    "            graph[j].add((i, w * (k + 1)))\n",
    "        for j, w in enumerate(appleCost):\n",
    "            graph[0].add((j + 1, w))\n",
    "\n",
    "        answer = [100000] * (n + 1)\n",
    "        apple = []\n",
    "        answer[0] = 0\n",
    "        queue = [(0, 0)]\n",
    "        while len(queue) != 0:\n",
    "            nextW, nextP = heapq.heappop(queue)\n",
    "            if nextW > answer[nextP]:\n",
    "                continue\n",
    "            for each, eachW in graph[nextP]:\n",
    "                tmp = nextW + eachW\n",
    "                if answer[each] > tmp:\n",
    "                    answer[each] = tmp\n",
    "                    heapq.heappush(queue, (tmp, each))\n",
    "\n",
    "        return answer[1:]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in roads:\n",
    "            g[u - 1].append((v - 1, w))\n",
    "            g[v - 1].append((u - 1, w))\n",
    "        def dijkstra(i):\n",
    "            pq, d, res = [(0, i)], defaultdict(int), inf\n",
    "            while pq:\n",
    "                w, node = heappop(pq)\n",
    "                if node not in d:\n",
    "                    d[node] = w + appleCost[node]\n",
    "                    res = min(res, d[node])\n",
    "                    for nei, weight in g[node]:\n",
    "                        heappush(pq, (w + weight * (k + 1), nei))\n",
    "            return res\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\r\n",
    "        g = defaultdict(list)\r\n",
    "        for a, b, cost in roads:\r\n",
    "            g[a - 1].append([b - 1, cost])\r\n",
    "            g[b - 1].append([a - 1, cost])\r\n",
    "        \r\n",
    "        def dijkstra(start: int):\r\n",
    "            ans = float('inf')\r\n",
    "            dist = [float('inf')] * n\r\n",
    "            dist[start] = 0\r\n",
    "            q = [(0, start)]\r\n",
    "            while q:\r\n",
    "                cost, x = heapq.heappop(q)\r\n",
    "                ans = min(ans, cost * (k + 1) + appleCost[x])\r\n",
    "                if dist[x] < cost:\r\n",
    "                    continue\r\n",
    "                for y, cost in g[x]:\r\n",
    "                    d = dist[x] + cost\r\n",
    "                    if d < dist[y]:\r\n",
    "                        dist[y] = d\r\n",
    "                        heapq.heappush(q, (d, y))\r\n",
    "            return ans\r\n",
    "        \r\n",
    "        ans = [0] * n\r\n",
    "        for i in range(n):\r\n",
    "            ans[i] = dijkstra(i)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in roads:\n",
    "            g[u - 1].append((v - 1, w))\n",
    "            g[v - 1].append((u - 1, w))\n",
    "        def dijkstra(i):\n",
    "            pq, d = [(0, i)], defaultdict(int)\n",
    "            while pq:\n",
    "                w, node = heappop(pq)\n",
    "                if node not in d:\n",
    "                    d[node] = w + appleCost[node]\n",
    "                    for nei, weight in g[node]:\n",
    "                        heappush(pq, (w + weight * (k + 1), nei))\n",
    "            return min(d.values())\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        def dijkstra(i):\n",
    "            pq, d, g = [(0, i)], defaultdict(int), defaultdict(list)\n",
    "            for u, v, w in roads:\n",
    "                g[u - 1].append((v - 1, w))\n",
    "                g[v - 1].append((u - 1, w))\n",
    "            while pq:\n",
    "                w, node = heappop(pq)\n",
    "                if node not in d:\n",
    "                    d[node] = w + appleCost[node]\n",
    "                    for nei, weight in g[node]:\n",
    "                        heappush(pq, (w + weight * (k + 1), nei))\n",
    "            return min(d.values())\n",
    "        return [dijkstra(i) for i in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\r\n",
    "        g = collections.defaultdict(list)\r\n",
    "        for a, b, c in roads:\r\n",
    "            g[a - 1].append((b - 1, c * (k + 1)))\r\n",
    "            g[b - 1].append((a - 1, c * (k + 1)))\r\n",
    "        visit = [0] * n\r\n",
    "        pq = sorted((c, i) for i, c in enumerate(appleCost))\r\n",
    "        while pq:\r\n",
    "            c, u = heapq.heappop(pq)\r\n",
    "            if visit[u]:\r\n",
    "                continue\r\n",
    "            visit[u] = 1\r\n",
    "            for v, nc in g[u]:\r\n",
    "                if appleCost[v] > c + nc:\r\n",
    "                    appleCost[v] = c + nc\r\n",
    "                    heapq.heappush(pq, (appleCost[v], v))\r\n",
    "        return appleCost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b, w in roads:\n",
    "            g[a - 1].append([b - 1, (k + 1) * w])\n",
    "            g[b - 1].append([a - 1, (k + 1) * w])\n",
    "        ans = [inf] * n \n",
    "\n",
    "        def dij(start):\n",
    "            dis = [inf] * n \n",
    "            h = [[start, 0]]\n",
    "            while h:\n",
    "                a, d = heappop(h)\n",
    "                if d >= dis[a]:\n",
    "                    continue\n",
    "                dis[a] = d \n",
    "                for nxt, delta in g[a]:\n",
    "                    if dis[nxt] > delta + dis[a]:\n",
    "                        heappush(h, [nxt, delta + dis[a]])\n",
    "            return dis \n",
    "        \n",
    "        for i in range(n):\n",
    "            dis = dij(i)\n",
    "            for j in range(n):\n",
    "                ans[j] = min(ans[j], dis[j] + appleCost[i])\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in roads:\n",
    "            g[a - 1].append([b - 1, cost])\n",
    "            g[b - 1].append([a - 1, cost])\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            ans = inf\n",
    "            dist = [inf] * n\n",
    "            dist[start] = 0\n",
    "            q = [(0, start)]\n",
    "            while q:\n",
    "                cost, node = heapq.heappop(q)\n",
    "                ans = min(ans, cost * (k + 1) + appleCost[node])\n",
    "                # if dist[node] < cost:\n",
    "                #     continue\n",
    "                for nei, cost in g[node]:\n",
    "                    d = dist[node] + cost\n",
    "                    if d < dist[nei]:\n",
    "                        dist[nei] = d\n",
    "                        heapq.heappush(q, (d, nei))\n",
    "            return ans\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        ad=collections.defaultdict(list)\n",
    "\n",
    "        for s,e,v in roads:\n",
    "            ad[s].append([v,e])\n",
    "            ad[e].append([v,s])\n",
    "        ans=[]\n",
    "        for s in range(1,n+1):\n",
    "            dis={i:float(\"inf\") for i in range(1,n+1)}\n",
    "            dis[s]=0\n",
    "            heap=[]\n",
    "            hq.heappush(heap,[0,s])\n",
    "            vis=[0]*(n+1)\n",
    "            while heap:\n",
    "                d,cur=hq.heappop(heap)\n",
    "                if vis[cur]==1:\n",
    "                    continue\n",
    "                vis[cur]=1\n",
    "                for nexd,nex in ad[cur]:\n",
    "                    if vis[nex]==0:\n",
    "                        if d+nexd<dis[nex]:\n",
    "                            dis[nex]=d+nexd\n",
    "                            hq.heappush(heap,[d+nexd,nex])\n",
    "            mx=float(\"inf\")\n",
    "            for x in dis:\n",
    "                tmp=dis[x]+k*dis[x]+appleCost[x-1]\n",
    "                if tmp<mx:\n",
    "                    mx=tmp\n",
    "            ans.append(mx)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self,n:int,roads:List[List[int]],appleCost:List[int],k:int):\n",
    "        INF=0x3f3f3f3f3f3f3f3f\n",
    "        adj=[[] for _ in range(0,n+1)]                    #邻接表\n",
    "        for i in range(0,len(roads)):      #遍历roads建立邻接表\n",
    "            a,b=roads[i][0],roads[i][1]     #<a,b>:w\n",
    "            w=(k+1)*roads[i][2]\n",
    "            adj[a].append([b,w])\n",
    "            adj[b].append([a,w])\n",
    "        for i in range(1,n+1):         #建超级源点的边\n",
    "            adj[0].append([i,appleCost[i-1]])\n",
    "            adj[i].append([0,appleCost[i-1]])\n",
    "        dist=[INF for _ in range(0,n+1)]\n",
    "        dist[0]=0\n",
    "        pqu=[]                          #定义小根堆pqu,元素为[length,vno]\n",
    "        heapq.heappush(pqu,[0,0])      #源点元素进队\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            u=e[1]                      #出队顶点u\n",
    "            for edj in adj[u]:\n",
    "                v,w=edj[0],edj[1]\n",
    "                if dist[v]>dist[u]+w:    #边松驰\n",
    "                    dist[v]=dist[u]+w\n",
    "                    heapq.heappush(pqu,[dist[v],v])      #顶点v元素进队\n",
    "        ans=[0]*n\n",
    "        for i in range(1,n+1):\n",
    "            ans[i-1]=dist[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self,n:int,roads:List[List[int]],appleCost:List[int],k:int):\n",
    "        INF=0x3f3f3f3f3f3f3f3f\n",
    "        adj=[[] for _ in range(0,n+1)]                    #邻接表\n",
    "        for i in range(0,len(roads)):      #遍历roads建立邻接表\n",
    "            a,b=roads[i][0],roads[i][1]     #<a,b>:w\n",
    "            w=(k+1)*roads[i][2]\n",
    "            adj[a].append([b,w])\n",
    "            adj[b].append([a,w])\n",
    "        for i in range(1,n+1):         #建超级源点的边\n",
    "            adj[0].append([i,appleCost[i-1]])\n",
    "            adj[i].append([0,appleCost[i-1]])\n",
    "        dist=[INF for _ in range(0,n+1)]\n",
    "        dist[0]=0\n",
    "        pqu=[]                          #定义小根堆pqu,元素为[length,vno]\n",
    "        heapq.heappush(pqu,[0,0])      #源点元素进队\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            u=e[1]                      #出队顶点u\n",
    "            for edj in adj[u]:\n",
    "                v,w=edj[0],edj[1]\n",
    "                if dist[v]>dist[u]+w:    #边松驰\n",
    "                    dist[v]=dist[u]+w\n",
    "                    heapq.heappush(pqu,[dist[v],v])      #顶点v元素进队\n",
    "        ans=[0]*n\n",
    "        for i in range(1,n+1):\n",
    "            ans[i-1]=dist[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        START = n  # 虚拟源点\n",
    "        adjList = [[] for _ in range(n + 1)]\n",
    "        for u, v, w in roads:\n",
    "            u, v = u - 1, v - 1\n",
    "            adjList[u].append((v, w * (k + 1)))\n",
    "            adjList[v].append((u, w * (k + 1)))\n",
    "        for i in range(n):\n",
    "            adjList[START].append((i, appleCost[i]))\n",
    "            adjList[i].append((START, appleCost[i]))\n",
    "        dist = dijkstra(n + 1, adjList, START)\n",
    "        return dist[:-1]\n",
    "\n",
    "\n",
    "def dijkstra(n: int, adjList: Sequence[Sequence[Tuple[int, int]]], start: int) -> List[int]:\n",
    "    dist = [INF] * n\n",
    "    dist[start] = 0\n",
    "    pq = [(0, start)]\n",
    "\n",
    "    while pq:\n",
    "        curDist, cur = heappop(pq)\n",
    "        if dist[cur] < curDist:\n",
    "            continue\n",
    "        for next, weight in adjList[cur]:\n",
    "            cand = dist[cur] + weight\n",
    "            if cand < dist[next]:\n",
    "                dist[next] = cand\n",
    "                heappush(pq, (dist[next], next))\n",
    "    return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self,n:int,roads:List[List[int]],appleCost:List[int],k:int):\n",
    "        INF=0x3f3f3f3f3f3f\n",
    "        adj=[[] for _ in range(0,n+1)]                    #邻接表\n",
    "        for i in range(0,len(roads)):      #遍历roads建立邻接表\n",
    "            a,b=roads[i][0],roads[i][1]     #<a,b>:w\n",
    "            w=(k+1)*roads[i][2]\n",
    "            adj[a].append([b,w])\n",
    "            adj[b].append([a,w])\n",
    "        for i in range(1,n+1):         #建超级源点的边\n",
    "            adj[0].append([i,appleCost[i-1]])\n",
    "            adj[i].append([0,appleCost[i-1]])\n",
    "        dist=[INF for _ in range(0,n+1)]\n",
    "        dist[0]=0\n",
    "        pqu=[]                          #定义小根堆pqu,元素为[length,vno]\n",
    "        heapq.heappush(pqu,[0,0])      #源点元素进队\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            u=e[1]                      #出队顶点u\n",
    "            for edj in adj[u]:\n",
    "                v,w=edj[0],edj[1]\n",
    "                if dist[v]>dist[u]+w:    #边松驰\n",
    "                    dist[v]=dist[u]+w\n",
    "                    heapq.heappush(pqu,[dist[v],v])      #顶点v元素进队\n",
    "        ans=[0]*n\n",
    "        for i in range(1,n+1):\n",
    "            ans[i-1]=dist[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param roads:\n",
    "        :param appleCost:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 ={}\n",
    "        for k1,v in enumerate(appleCost):\n",
    "            m1[k1+1] = v\n",
    "        m2 = defaultdict(list)\n",
    "        for i in roads:\n",
    "            m2[i[0]].append((i[1], i[2]))\n",
    "            m2[i[1]].append((i[0], i[2]))\n",
    "        minv = min(appleCost)\n",
    "        dq = deque()\n",
    "        for i in m1:\n",
    "\n",
    "            dq.append((i, m1[i]))\n",
    "        m3 = {}\n",
    "        while dq:\n",
    "            first, v1 = dq.popleft()\n",
    "            ref = min(v1, m1[first])\n",
    "            if first not in m3:\n",
    "                m3[first] = ref\n",
    "            else:\n",
    "                if m3[first] <= ref:\n",
    "                    continue\n",
    "                m3[first] = ref\n",
    "            for i in m2[first]:\n",
    "                vv = i\n",
    "                newp = vv[1] * (k+1)\n",
    "                dq.append((vv[0], ref + newp))\n",
    "        ret = []\n",
    "        for i in range(1, n+1):\n",
    "            ret.append(m3.get(i, m1.get(i)))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 状压DP，dp[i][j]表示前i个左侧数已经根j所表示的二进制位的右侧的数匹配时，后续完成两组点连通的最小代价\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "\n",
    "        m,  n = len(cost), len(cost[0])\n",
    "        dp = [[-1] * (1 << n) for _ in range(m + 1)]\n",
    "\n",
    "        mask = (1 << n) - 1\n",
    "        minCostY = [10 ** 9] * n\n",
    "        # print(minCostY)\n",
    "        for row in cost:\n",
    "            for j, c in enumerate(row):\n",
    "                minCostY[j] = min(minCostY[j], c)\n",
    "\n",
    "        def dfs(i: int, choose: int) -> int:\n",
    "            # nonlocal dp\n",
    "            if dp[i][choose] >= 0:\n",
    "                return dp[i][choose]\n",
    "            if i == m:\n",
    "                oriChoose = choose\n",
    "                choose = (choose ^ mask) & mask\n",
    "                res = 0\n",
    "                while choose:\n",
    "                    # print(choose & (-choose))\n",
    "                    lst = (choose & (-choose)).bit_length() - 1\n",
    "                    # print(lst)\n",
    "                    res += minCostY[lst]\n",
    "                    choose &= (choose - 1)\n",
    "                dp[i][oriChoose] = res\n",
    "                return res\n",
    "            res = 10 ** 9\n",
    "            for j in range(n):\n",
    "                res = min(res,  cost[i][j] + dfs(i + 1, choose | (1 << j)))\n",
    "            dp[i][choose] = res\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        ##矩阵每行每列都至少选一个坐标\n",
    "        n,m=len(cost),len(cost[0])\n",
    "        minCost=[min(col) for col in zip(*cost)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,nodes):\n",
    "            if i<0:\n",
    "                return sum(c for k,c in enumerate(minCost) if nodes&(1<<k))\n",
    "            return min(dfs(i-1,nodes&~(1<<k))+c for k,c in enumerate(cost[i]))\n",
    "        return dfs(n-1,(1<<m)-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectTwoGroups(self, cost: List[List[int]]) -> int:\n",
    "        i = len(cost)\n",
    "        j = len(cost[0])\n",
    "\n",
    "        minCost = [min(i) for i in zip(*cost)]\n",
    "\n",
    "        @cache \n",
    "        def dp(i, rest):\n",
    "            if i < 0: return sum(c for k, c in enumerate(minCost) if rest >> k & 1)\n",
    "            \n",
    "            res = inf\n",
    "            for n in range(j):\n",
    "                res = min(res, dp(i - 1, rest & ~(1 << n)) + cost[i][n])\n",
    "            return res\n",
    "        \n",
    "        return dp(i - 1, (1 << j) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        m = len(cuts)\n",
    "        cuts = [0]+cuts+[n]\n",
    "        dp = [[0]*(m+2) for _ in range(m+2)]\n",
    "        \n",
    "        for i in range(m+1,-1,-1):\n",
    "            for j in range(i+2,m+2):\n",
    "                    minn = 10**9\n",
    "                    for k in range(i+1,j):\n",
    "                        minn = min(minn,dp[k][j]+dp[i][k])\n",
    "                    dp[i][j] = minn + cuts[j]-cuts[i]\n",
    "        return dp[0][m+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        m = len(cuts)\n",
    "        cuts.sort()\n",
    "        cuts = [0] + cuts + [n]\n",
    "        dp = [[0]*(m+2) for _ in range(m+2)]\n",
    "\n",
    "        for L in range(3, m+3):\n",
    "            for i in range(m+2-L+1):\n",
    "                l,r = i,i+L-1\n",
    "                dp[l][r] = float('inf')\n",
    "                for k in range(l+1,r):\n",
    "                    dp[l][r] = min(dp[l][r], dp[l][k]+dp[k][r])\n",
    "                dp[l][r] += (cuts[r] - cuts[l])\n",
    "        return dp[0][m+1]\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts = [0] + sorted(cuts) + [n]\n",
    "\n",
    "        len_ = len(cuts)\n",
    "        f = [[0] * len_ for _ in range(len_)]  # i 有n个状态, 又有i + 1, 所以大小为n + 1\n",
    "        for i in range(len_ - 3, -1, -1):\n",
    "            for j in range(i + 2, len_):\n",
    "                f[i][j] = min(f[i][k] + f[k][j] + cuts[j] - cuts[i] for k in range(i + 1, j))\n",
    "                # res = inf \n",
    "                # for k in range(i + 1, j):\n",
    "                #     cut = cuts[k]\n",
    "                #     res = min(res, f[i][k] + f[k][j] + cuts[j] - cuts[i])\n",
    "                # f[i][j] = res\n",
    "                \n",
    "        return f[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts = [0] + sorted(cuts) + [n]\n",
    "\n",
    "        len_ = len(cuts)\n",
    "        f = [[0] * len_ for _ in range(len_)]  # i 有n个状态, 又有i + 1, 所以大小为n + 1\n",
    "        for i in range(len_ - 3, -1, -1):\n",
    "            for j in range(i + 2, len_):\n",
    "                f[i][j] = min(f[i][k] + f[k][j] + cuts[j] - cuts[i] for k in range(i + 1, j))\n",
    "                # res = inf \n",
    "                # for k in range(i + 1, j):\n",
    "                #     cut = cuts[k]\n",
    "                #     res = min(res, f[i][k] + f[k][j] + cuts[j] - cuts[i])\n",
    "                # f[i][j] = res\n",
    "                \n",
    "        return f[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()  \n",
    "        cuts.insert(0,0)\n",
    "        cuts.append(n)\n",
    "        m = len(cuts)\n",
    "        dp = [[0] * m for _ in range(m)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(i + 1, m):\n",
    "                dp[i][j] = (j - i) * (cuts[j] - cuts[i])\n",
    "                for k in range(i + 1, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i])\n",
    "        \n",
    "        return dp[0][-1] - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts = [0] + sorted(cuts) + [n]\n",
    "\n",
    "        x = len(cuts)\n",
    "        f = [[0] * x for _ in range(x)]\n",
    "        for i in range(x - 3, -1, -1):\n",
    "            for j in range(i + 2, x):\n",
    "                res = inf\n",
    "                for k in range(i + 1, j):\n",
    "                    res = min(res, f[i][k] + f[k][j] + cuts[j] - cuts[i])\n",
    "                f[i][j] = res if res != inf else 0\n",
    "\n",
    "        return f[0][x - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts = [0] + sorted(cuts) + [n]\n",
    "        x = len(cuts)\n",
    "        f = [[0] * x for _ in range(x)]\n",
    "\n",
    "        for i in range(x - 3, -1, -1):\n",
    "            for j in range(i + 2, x):\n",
    "                res = inf\n",
    "                for k in range(i + 1, j):\n",
    "                    res = min(res, f[i][k] + f[k][j] + cuts[j] - cuts[i])\n",
    "                f[i][j] = res if res != inf else 0\n",
    "        return f[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        nums = [0] + cuts + [n]\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i-1][i] = 0\n",
    "            for j in range(i-2, -1, -1):\n",
    "                best = math.inf\n",
    "                for k in range(j+1, i):\n",
    "                    best = min(best, dp[j][k] + dp[k][i])\n",
    "                dp[j][i] = best + nums[i] - nums[j]\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        m=len(cuts)\n",
    "        cuts.sort()\n",
    "        cuts.insert(0,0)\n",
    "        cuts.append(n)\n",
    "        m+=2\n",
    "        dp=[[-1]*m for i in range(m)]\n",
    "        def f(i,j):\n",
    "            if dp[i][j]!=-1:return dp[i][j]\n",
    "            if i==j-1:\n",
    "                dp[i][j]=0\n",
    "                return 0\n",
    "            fee=math.inf\n",
    "            for k in range(i+1,j):\n",
    "                fee=min(fee,f(i,k)+f(k,j)+cuts[j]-cuts[i])\n",
    "            dp[i][j]=fee\n",
    "            return fee \n",
    "        return f(0,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        m = len(cuts)\n",
    "        cuts.sort()\n",
    "        arr = [0]*(m+2)\n",
    "        for i in range(m):\n",
    "            arr[i+1] = cuts[i]\n",
    "        arr[m+1] = n\n",
    "        def f(arr,l,r,dp):\n",
    "            if dp[l][r]!=-1:\n",
    "                return dp[l][r]\n",
    "            if l>r:\n",
    "                return 0\n",
    "            if l==r:\n",
    "                return arr[r+1]-arr[l-1]\n",
    "            ans = float('inf')\n",
    "            for k in range(l,r+1):\n",
    "                ans = min(ans,f(arr,l,k-1,dp)+f(arr,k+1,r,dp))\n",
    "            ans += arr[r+1]-arr[l-1]\n",
    "            dp[l][r] = ans\n",
    "            return ans\n",
    "        dp = [[-1]*(m+2) for _ in range(m+2)]\n",
    "        return f(arr,1,m,dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        arr = []\n",
    "        cuts = [0] + cuts + [n]\n",
    "        for x, y in pairwise(cuts):\n",
    "            arr.append(y - x)\n",
    "        print(arr)\n",
    "        m = len(arr)\n",
    "        pre = [0]\n",
    "        for x in arr: pre.append(pre[-1] + x)\n",
    "        print(pre)\n",
    "        # 区间dp\n",
    "        # 定义f[i][j]表示合并i-j的最小花费\n",
    "        # f[i]][j] = min(f[i][mid] + f[mid][j] + sum(arr[i:j+1]))\n",
    "        # f[i][i] = arr[i]\n",
    "        f = [[inf] * m for _ in range(m)]\n",
    "        for i in range(m): f[i][i] = 0\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(i + 1, m):\n",
    "                for mid in range(i, j):\n",
    "                    f[i][j] = min(f[i][j], f[i][mid] + f[mid + 1][j] + sum(arr[i: j + 1]))\n",
    "        print(f)\n",
    "        return f[0][m - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        blocks=[cuts[0]]\n",
    "        for i in range(len(cuts)-1):\n",
    "            blocks.append(cuts[i+1]-cuts[i])\n",
    "        blocks.append(n-cuts[-1])\n",
    "        m=len(blocks)\n",
    "        cost=[[0]*m for _ in range(m)]\n",
    "        dp=[[float('inf')]*m for _ in range(m)]\n",
    "        #dp[i][j] 表示将区间[i,j]的木棍合并为一根的最小费用\n",
    "        #dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+length(i,j))\n",
    "        for i in range(m):\n",
    "            cost[i][i]=blocks[i]\n",
    "            dp[i][i]=0\n",
    "        for i in range(m):\n",
    "            for j in range(i+1,m):\n",
    "                cost[i][j]=cost[i][j-1]+blocks[j]\n",
    "        \n",
    "        for len_ in range(2,m+1):\n",
    "            for l in range(m):\n",
    "                r=l+len_-1\n",
    "                if r>=m:continue\n",
    "                for k in range(l,r):\n",
    "                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+cost[l][r])\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        # 先想暴力 基础case\n",
    "        cuts.sort()\n",
    "        # 每次选择一个分割点\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if r - l < 2:\n",
    "                return 0\n",
    "            # 顶多转移是log的\n",
    "            index1 = bisect_right(cuts, l)\n",
    "            index2 = bisect_left(cuts, r)\n",
    "            if index1 >= index2:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in cuts[index1:index2]:\n",
    "                cur = dfs(l, k) + dfs(k, r) + r - l\n",
    "                res = cur if cur < res else res\n",
    "            return res\n",
    "        \n",
    "\n",
    "        ans = dfs(0, n)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        cutdict = {x:ind for ind, x in enumerate(cuts)}\n",
    "        cutdict[0] = -1\n",
    "        cutdict[n] = len(cuts) \n",
    "        @lru_cache(None)\n",
    "        def myfun(st, ed):\n",
    "            ind_st, ind_ed = cutdict[st], cutdict[ed]\n",
    "            if ind_ed - ind_st == 1: return 0\n",
    "            b = float(\"inf\")\n",
    "            for i in range(ind_st+1, ind_ed):\n",
    "                a = myfun(st, cuts[i]) + myfun(cuts[i], ed)\n",
    "                b = min(a, b)\n",
    "            return (b + ed - st)\n",
    "        ans = myfun(0, n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        newcuts = [0] + sorted(cuts) + [n]\n",
    "        m = len(newcuts)\n",
    "        dp = [[0] * m for _ in range(m)]\n",
    "        \n",
    "        for i in range(m-3, -1, -1):\n",
    "            for j in range(i+2, m):\n",
    "                res = inf \n",
    "                for k in range(i+1, j):\n",
    "                    res = min(res, dp[i][k] + dp[k][j] + newcuts[j] - newcuts[i])\n",
    "                dp[i][j] = res \n",
    "        \n",
    "        print(dp)\n",
    "        return dp[0][m-1]\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i + 1 >= j:\n",
    "        #         return 0\n",
    "        #     res = inf\n",
    "        #     for k in range(i+1, j):\n",
    "        #         res = min(res, dfs(i, k) + dfs(k, j) + newcuts[j] - newcuts[i])\n",
    "        #     return res\n",
    "\n",
    "        # return dfs(0, len(newcuts) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.extend([0,n])\n",
    "        cuts.sort()\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dp(start,end):\n",
    "            res=[]\n",
    "            for idx in range(start+1,end): # 接下来的一刀切在cuts[idx]这个位置\n",
    "                res.append(dp(start,idx)+dp(idx,end))\n",
    "            return min(res)+cuts[end]-cuts[start] if res else 0\n",
    "        return dp(0,len(cuts)-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def search(l, r):\n",
    "            ret = float(\"inf\")\n",
    "            flag = False\n",
    "            for c in cuts:\n",
    "                if c > l and c < r:\n",
    "                    flag = True\n",
    "                    tmp = r - l + search(l, c) + search(c, r)\n",
    "                    ret = min(ret, tmp)\n",
    "            if not flag:\n",
    "                return 0\n",
    "            return ret\n",
    "        return search(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.append(0)\n",
    "        cuts.append(n)\n",
    "        cuts.sort()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def cut(i, j):  # 直接用arr(i, j)切割的最小和\n",
    "            if i > j - 2:\n",
    "                return 0\n",
    "            ans = float('inf')\n",
    "\n",
    "            for k in range(i + 1, j):  # 遍历切割点\n",
    "                ans = min(ans, cut(i, k) + cut(k, j) + cuts[j] - cuts[i])\n",
    "            return ans\n",
    "\n",
    "        return cut(0, len(cuts) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        arr = [0] + sorted(cuts) + [n]\n",
    "        @lru_cache(None)\n",
    "        def f(a, b):\n",
    "            if a == b - 1:\n",
    "                return 0\n",
    "            return min((f(a, i) + f(i, b)) for i in range(a + 1, b)) + arr[b] - arr[a]\n",
    "        return f(0, len(arr) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        s={}#加一个字典，保存子结果，动态规划\n",
    "        cuts.sort()\n",
    "        cuts=[0]+cuts+[n]\n",
    "        l=len(cuts)\n",
    "        '''\n",
    "        从函数需要的参数可以看出，原函数需要最一般的参数，而新的函数只需要开头结尾，\n",
    "        因为它都在cuts,n这种需要情况下计算，只计算一种特殊情况就有可以保存子结果的优势\n",
    "        '''\n",
    "        def helper(st,ed):\n",
    "            if (st,ed) in s:\n",
    "                return s[(st,ed)]#加入字典提高效率的关键：有的话立刻返回\n",
    "            if ed-st==1:\n",
    "                s[(st,ed)]=0 #子结果入字典\n",
    "                return 0\n",
    "            elif ed-st==2:\n",
    "                s[(st,ed)]=cuts[ed]-cuts[st] #子结果入字典\n",
    "                return cuts[ed]-cuts[st]\n",
    "            else:\n",
    "                temp=float('inf')\n",
    "                for i in range(st+1,ed):\n",
    "                    temp=min(temp,helper(st,i)+helper(i,ed))\n",
    "                temp=temp+cuts[ed]-cuts[st]\n",
    "                s[(st,ed)]=temp #子结果入字典\n",
    "                return temp\n",
    "        return helper(0,l-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        cuts = [0] + cuts + [n]\n",
    "        n_cuts = len(cuts)\n",
    "        dp = {}\n",
    "        def search(l, r):\n",
    "            if l+1 == r:\n",
    "                return 0\n",
    "            res = 1e10\n",
    "            for i in range(l+1, r):\n",
    "                if (cuts[l], cuts[i]) not in dp:\n",
    "                    dp[(cuts[l], cuts[i])] = search(l, i)\n",
    "                if (cuts[i], cuts[r]) not in dp:\n",
    "                    dp[(cuts[i], cuts[r])] = search(i, r)\n",
    "                cost_left = dp[(cuts[l], cuts[i])]\n",
    "                cost_right = dp[(cuts[i], cuts[r])]\n",
    "                res = min(res, cost_left+cost_right)\n",
    "            return cuts[r] - cuts[l] + res\n",
    "        dp[(0,n)] = search(0, n_cuts-1)\n",
    "        return dp[(0,n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        A = [0] + sorted(cuts) + [n]\n",
    "        @lru_cache(None)\n",
    "        def dp(i,j):\n",
    "            if i+1>=j:\n",
    "                return 0\n",
    "            return A[j]-A[i] + min(dp(i,k) +dp(k,j) for k in range(i+1,j))\n",
    "        return dp(0,len(A)-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        d={}\n",
    "        \n",
    "            \n",
    "        def cut(l,r,cuts):\n",
    "            if len(cuts)==0:\n",
    "                return 0\n",
    "            if len(cuts)==1:\n",
    "                return r-l\n",
    "            tmp=float('inf')\n",
    "            \n",
    "            for i in range(len(cuts)):\n",
    "                \n",
    "                \n",
    "                v1,v2=(l,cuts[i]),(cuts[i],r)\n",
    "                if v1 not in d:\n",
    "                    d[v1]=cut(l,cuts[i],cuts[:i])\n",
    "                if v2 not in d:\n",
    "                    d[v2]=cut(cuts[i],r,cuts[i+1:])\n",
    "                    \n",
    "                cur=d[v1]+d[v2]+r-l\n",
    "                \n",
    "                tmp=min(cur,tmp)\n",
    "            return tmp\n",
    "                \n",
    "                \n",
    "        return cut(0,n,cuts)\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        dp = {}\n",
    "        cuts.insert(0, 0)\n",
    "        cuts.append(n)\n",
    "\n",
    "        def find(i, j):\n",
    "            if (i, j) in dp:\n",
    "                return dp[(i, j)]\n",
    "            if i+1 >= j:\n",
    "                dp[(i, j)] = 0\n",
    "                return 0\n",
    "            \n",
    "            if j == i+2:\n",
    "                dp[(i, j)] = cuts[j] - cuts[i]\n",
    "                return dp[(i, j)]\n",
    "            \n",
    "            best = None\n",
    "            for x in range(i+1, j):\n",
    "                cur = find(i, x) + find(x, j) + cuts[j] - cuts[i]\n",
    "                if not best or cur < best:\n",
    "                    best = cur\n",
    "            \n",
    "            dp[(i, j)] = best\n",
    "            return best\n",
    "        \n",
    "        return find(0, len(cuts)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "\n",
    "        m = len(cuts)\n",
    "        cuts.sort()\n",
    "        answerdict = {}\n",
    "        def _minCost(i, j):\n",
    "            if j - i == 1:\n",
    "                return 0\n",
    "            if (i, j) in answerdict:\n",
    "                return answerdict[(i, j)]\n",
    "            if i == -1:\n",
    "                l = 0\n",
    "            else:\n",
    "                l = cuts[i]\n",
    "            if j == m:\n",
    "                r = n\n",
    "            else:\n",
    "                r = cuts[j]\n",
    "    \n",
    "            answer = min([_minCost(i, k)+_minCost(k, j) for k in range(i+1, j)]) + r - l\n",
    "            answerdict[(i, j)] = answer\n",
    "            return answer\n",
    "        \n",
    "        return _minCost(-1, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, m: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(nums)\n",
    "        DP = [[10 ** 9 for _ in range(n)] for _ in range(n)]\n",
    "        def solve(l: int, r: int) -> int:\n",
    "            if l > r: return 0\n",
    "            x = nums[l - 1] if l > 0 else 0\n",
    "            y = nums[r + 1] if r < n - 1 else m\n",
    "            if l == r: return y - x\n",
    "            if DP[l][r] != 10 ** 9: return DP[l][r]\n",
    "            for i in range(l, r + 1):\n",
    "                DP[l][r] = min(DP[l][r],\n",
    "                        y - x + solve(l, i - 1) + solve(i + 1, r))\n",
    "            return DP[l][r]\n",
    "        return solve(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def cut(l, r, i, j):  # 在(l,r)直接用arr[i, j]切割的最小和\n",
    "            if i > j:\n",
    "                return 0\n",
    "            elif i == j:\n",
    "                return r - l\n",
    "            ans = n * (j - i + 1)\n",
    "            for k in range(i, j + 1):  # 遍历切割点\n",
    "                ans = min(ans, cut(l, cuts[k], i, k - 1) + cut(cuts[k], r, k + 1, j) + r - l)\n",
    "            return ans\n",
    "\n",
    "        return cut(0, n, 0, len(cuts) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    \n",
    "    def minCost(self, lens: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        @lru_cache(None)\n",
    "        def dfs(head,tail,l,r):\n",
    "            # print(head,tail,l,r)\n",
    "            if l>=r:\n",
    "                return 0\n",
    "            if l+1==r:\n",
    "                return tail-head\n",
    "            res=2**31-1\n",
    "            \n",
    "            for i in range(l,r):\n",
    "                res=min(res,tail-head+dfs(head,cuts[i],l,i)+dfs(cuts[i],tail,i+1,r))\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,lens,0,len(cuts))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts = [0] + sorted(cuts) + [n]\n",
    "        memo = {}\n",
    "        for i in range(1, len(cuts)):\n",
    "            memo[(cuts[i-1], cuts[i])] = cuts[i] - cuts[i-1]\n",
    "        def dp(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            ans = float(\"inf\")\n",
    "            for k in cuts:\n",
    "                if i < k < j:\n",
    "                    ans = min(ans, dp(i, k) + dp(k, j) + j - i)\n",
    "            memo[(i, j)] = ans\n",
    "            return memo[(i, j)]\n",
    "        return dp(0, n) - n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def cut(l, r, i, j):  # 在(l,r)直接用arr[i, j]切割的最小和\n",
    "            if i > j:\n",
    "                return 0\n",
    "            elif i == j:\n",
    "                return r - l\n",
    "            ans = n * (j - i + 1)\n",
    "            for k in range(i, j + 1):  # 遍历切割点\n",
    "                ans = min(ans, cut(l, cuts[k], i, k - 1) + cut(cuts[k], r, k + 1, j) + r - l)\n",
    "            return ans\n",
    "\n",
    "        return cut(0, n, 0, len(cuts) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "import json\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts) -> int:\n",
    "        cuts=sorted(cuts)\n",
    "        @lru_cache(None)\n",
    "        def dp(l,r):\n",
    "            tmpcuts=[]\n",
    "            for c in cuts:\n",
    "                if c>l and c<r:\n",
    "                    tmpcuts.append(c)\n",
    "            if tmpcuts == []:\n",
    "                return 0\n",
    "            mincost=float('inf')\n",
    "            for idx,c in enumerate(tmpcuts):\n",
    "                mincost=min(mincost,dp(l,c)+dp(c,r))\n",
    "            return mincost+r-l\n",
    "            \n",
    "        return dp(0,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        arr = [0] + sorted(cuts) + [n]\n",
    "        dic={}\n",
    "        def f(a, b):\n",
    "            if a == b - 1:\n",
    "                dic[(a,b)]=0\n",
    "                return 0\n",
    "            elif (a,b) in dic:\n",
    "                return dic[(a,b)]\n",
    "            dic[(a,b)]=min((f(a, i) + f(i, b)) for i in range(a + 1, b)) + arr[b] - arr[a]\n",
    "            return dic[(a,b)]\n",
    "        return f(0, len(arr) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts = sorted(cuts)\n",
    "        hashset = set(cuts)\n",
    "        cuts = [0] + cuts + [n]\n",
    "        hashmap = dict(zip(cuts, range(len(cuts))))\n",
    "        @lru_cache(None)\n",
    "        def solve(start, end):\n",
    "            cuts_ = cuts[hashmap[start]+1: hashmap[end]]\n",
    "            if len(cuts_) == 0: return 0\n",
    "            elif len(cuts_) == 1: return end - start\n",
    "            ans = float('inf')\n",
    "            for cutpoint in cuts_:\n",
    "                left = solve(start, cutpoint)\n",
    "                right = solve(cutpoint, end)\n",
    "                ans = min(ans, end - start + left + right)\n",
    "            return ans \n",
    "        return solve(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        rod = [0]+cuts+[n]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def cut_rod(left,right):\n",
    "            if rod.index(right)-rod.index(left)<=1 :\n",
    "                return 0\n",
    "            res = float(\"inf\")\n",
    "            for i in cuts[rod.index(left):rod.index(right)]:\n",
    "                total = right-left\n",
    "                if left<i<right:\n",
    "                    #flag = true\n",
    "                    total += cut_rod(left,i)+cut_rod(i,right)\n",
    "                    res = min(res,total)\n",
    "            return res\n",
    "        return cut_rod(0,n)\n",
    "\n",
    "        # m = len(cuts)\n",
    "        # cuts = [0] + sorted(cuts) + [n]\n",
    "        # f = [[0] * (m + 2) for _ in range(m + 2)]\n",
    "\n",
    "        # for i in range(m, 0, -1):\n",
    "        #     for j in range(i, m + 1):\n",
    "        #         f[i][j] = 0 if i == j else \\\n",
    "        #             min(f[i][k - 1] + f[k + 1][j] for k in range(i, j + 1))\n",
    "        #         f[i][j] += cuts[j + 1] - cuts[i - 1]\n",
    "        \n",
    "        # return f[1][m]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        cuts = list(chain([0], cuts, [n]))\n",
    "        cache = {}\n",
    "        inf = float('inf')\n",
    "        def recur(i, j):\n",
    "            if j <= i + 1: return 0\n",
    "            key = (i, j)\n",
    "            cached = cache.get(key)\n",
    "            if cached is not None: return cached\n",
    "            result = inf\n",
    "            for k in range(i+1, j):\n",
    "                result = min(result, recur(i, k)+recur(k, j))\n",
    "            result += cuts[j] - cuts[i]\n",
    "            cache[key] = result\n",
    "            return result\n",
    "        return recur(0, len(cuts)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        def dfs(cuts,i,j):\n",
    "            if  (i,j) in memo:\n",
    "                return memo[(i,j)]\n",
    "            if (j-i == 1):\n",
    "                return 0\n",
    "            ret = float('inf')\n",
    "            for k in range(i+1,j):\n",
    "                ret = min(ret, dfs(cuts,i,k)+dfs(cuts,k,j)+cuts[j]-cuts[i])\n",
    "            memo[(i,j)] = ret\n",
    "            return ret\n",
    "        memo = {}\n",
    "        cuts.sort()\n",
    "        cuts = [0] + cuts + [n]\n",
    "        return dfs(cuts,0,len(cuts)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        D={}\n",
    "        def DP(i,j,cuts):\n",
    "            if (i,j) in D: return D[(i,j)]\n",
    "            if j-i<=1: \n",
    "                D[(i,j)]=0\n",
    "                return D[(i,j)]\n",
    "            cc=[]\n",
    "            for x in cuts:\n",
    "                if x>i and x<j:\n",
    "                    cc.append(x)\n",
    "            if len(cc)==0: \n",
    "                D[(i,j)]=0\n",
    "                return D[(i,j)]\n",
    "            v=math.inf\n",
    "            for k in range(len(cc)):\n",
    "                v=min(v,DP(i,cc[k],cuts)+DP(cc[k],j,cuts)+j-i)\n",
    "            D[(i,j)]=v\n",
    "            return v\n",
    "        return DP(0,n,cuts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dfs(l,r):\n",
    "            if l+1 == r:\n",
    "                return 0\n",
    "            res = float('inf')\n",
    "            for i in range(l+1,r):\n",
    "                res =min(res,dfs(l,i)+dfs(i,r)+cuts[r]-cuts[l])\n",
    "            return res\n",
    "        cuts += [0,n]\n",
    "        cuts.sort()\n",
    "        return dfs(0,len(cuts)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i:int,j:int)->int:\n",
    "            if i == j -1:\n",
    "                return 0\n",
    "            base = cuts[j]-cuts[i] #现长度\n",
    "            result = 2**32\n",
    "            for k in range(i+1,j):\n",
    "                result = min(dfs(i,k)+dfs(k,j),result)\n",
    "            return result+base\n",
    "        cuts += [0,n]\n",
    "        cuts.sort()\n",
    "        # print(cuts)\n",
    "        return dfs(0,len(cuts)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.extend([0,n])\n",
    "        cuts.sort()\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dp(start,end):\n",
    "            res=[]\n",
    "            for idx in range(start+1,end): # 接下来的一刀切在cuts[idx]这个位置\n",
    "                res.append(dp(start,idx)+dp(idx,end))\n",
    "            return min(res)+cuts[end]-cuts[start] if res else 0\n",
    "        return dp(0,len(cuts)-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.extend([0,n])\n",
    "        cuts.sort()\n",
    "        lenCuts = len(cuts)\n",
    "        @cache\n",
    "        def dp(i,j):\n",
    "            if j-i<=1: return 0\n",
    "            res = float(\"inf\")\n",
    "            for m in range(i+1,j):\n",
    "                res = min(res,dp(i,m)+dp(m,j))\n",
    "            return res+cuts[j]-cuts[i]\n",
    "        return dp(0,lenCuts-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.extend([0,n])\n",
    "        cuts.sort()\n",
    "        lenCuts = len(cuts)\n",
    "        @cache\n",
    "        def dp(i,j):\n",
    "            if j-i<=1: return 0\n",
    "            res = float(\"inf\")\n",
    "            for m in range(i+1,j):\n",
    "                res = min(res,dp(i,m)+dp(m,j))\n",
    "            return res+cuts[j]-cuts[i]\n",
    "        return dp(0,lenCuts-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "\n",
    "        array = sorted([0] + cuts + [n])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def compute(left, right):\n",
    "\n",
    "            if left == right - 1:\n",
    "                return 0\n",
    "\n",
    "            res = float('inf')\n",
    "            for mid in range(left + 1, right):\n",
    "                res = min(res, compute(left, mid) + compute(mid, right))\n",
    "\n",
    "            return res + array[right] - array[left]\n",
    "\n",
    "        return compute(0, len(array) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        cuts = [0] + cuts +[n]\n",
    "        memo = {}\n",
    "        k = len(cuts)\n",
    "        def walk(start,end):\n",
    "            if (start,end) in memo:\n",
    "                return memo[(start,end)]\n",
    "            if end - start == 1:\n",
    "                memo[(end,start)] = 0\n",
    "                return 0\n",
    "            if end - start == 2:\n",
    "                memo[(start,end)] = cuts[end] - cuts[start]\n",
    "                return cuts[end] - cuts[start]\n",
    "            temp = float('inf')\n",
    "            for i in range(start+1,end):\n",
    "                temp = min(temp,walk(start,i)+walk(i,end))\n",
    "            temp += cuts[end] - cuts[start]\n",
    "            memo[(start,end)] = temp\n",
    "            return temp\n",
    "        return walk(0,k-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @cache\n",
    "        def solve(i, j):\n",
    "            if i + 1 >= j:\n",
    "                return 0\n",
    "            ans = float('inf')\n",
    "            for k in range(i + 1, j):\n",
    "                ans = min(ans, cuts[j] - cuts[i] + solve(i, k) + solve(k, j))\n",
    "            return ans\n",
    "\n",
    "        cuts.append(0)\n",
    "        cuts.append(n)\n",
    "        cuts.sort()\n",
    "        return solve(0, len(cuts) - 1)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        # 需要切开的位置在数组中,假设切开k\n",
    "        # 左边为l,右边记为r\n",
    "        # j为要切割处\n",
    "        if len(cuts) == 1:\n",
    "            return n\n",
    "        cuts.sort()\n",
    "        cuts = [0] + cuts + [n] # 添加首尾,变成把cuts划分为长短为2的对的最小成本\n",
    "        _len = len(cuts)\n",
    "        @lru_cache(None)\n",
    "        def dfs(l,r):\n",
    "            if l+1 == r:\n",
    "                return 0\n",
    "            elif l+2 == r: # 只用砍一刀\n",
    "                return cuts[r] - cuts[l]\n",
    "            res = inf\n",
    "            t = cuts[r]-cuts[l]\n",
    "            for i in range(l+1,r):\n",
    "                res = min(dfs(i,r)+dfs(l,i),res)\n",
    "            return res+t\n",
    "        return dfs(0,_len-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j,l,r):\n",
    "            if i==j:return 0 \n",
    "            ans=10**9\n",
    "            for k in range(i,j):\n",
    "                ans=min(ans,dfs(i,k,l,cuts[k])+dfs(k+1,j,cuts[k],r)+r-l)\n",
    "            return ans\n",
    "        cuts.sort()\n",
    "        return dfs(0,len(cuts),0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        m = len(cuts)\n",
    "\n",
    "        @cache\n",
    "        def dfs(l, r, cl, cr):\n",
    "            if cl > cr:\n",
    "                return 0\n",
    "            if cl == cr:\n",
    "                return r - l\n",
    "\n",
    "            ans = inf\n",
    "            for k in range(cl, cr+1):\n",
    "                ans = min(ans, dfs(l, cuts[k], cl, k-1) + dfs(cuts[k], r, k+1, cr))\n",
    "            return ans + r - l\n",
    "\n",
    "        return dfs(0, n, 0, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j,l,r):\n",
    "            if i==j:return 0 \n",
    "            ans=10**9\n",
    "            for k in range(i,j):\n",
    "                ans=min(ans,dfs(i,k,l,cuts[k])+dfs(k+1,j,cuts[k],r)+r-l)\n",
    "            return ans\n",
    "        cuts.sort()\n",
    "        return dfs(0,len(cuts),0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j,l,r):\n",
    "            if i==j:return 0 \n",
    "            ans=10**9\n",
    "            for k in range(i,j):\n",
    "                ans=min(ans,dfs(i,k,l,cuts[k])+dfs(k+1,j,cuts[k],r)+r-l)\n",
    "            return ans\n",
    "        cuts.sort()\n",
    "        return dfs(0,len(cuts),0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        @cache\n",
    "        def f(l,r,ll,rr):\n",
    "            if ll > rr:\n",
    "                return 0\n",
    "            k = r-l\n",
    "            ans = inf\n",
    "            for i in range(ll, rr+1):\n",
    "                t = cuts[i]\n",
    "                ans = min(ans, k + f(l, t, ll, i-1) + f(t, r, i+1, rr))\n",
    "            return ans\n",
    "        return f(0, n, 0, len(cuts)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        return (f := cache(lambda l, r: min((r - l + f(l, c) + f(c, r) for c in cuts[bisect_right(cuts, l):bisect_left(cuts, r)]), default = 0)))(0, n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j-i==1:\n",
    "                return 0\n",
    "            res=[]\n",
    "            for k in range(len(cuts)):\n",
    "                if i<cuts[k]<j:\n",
    "                    res.append(dfs(i,cuts[k])+dfs(cuts[k],j)+j-i)\n",
    "            if res==[]:\n",
    "                return 0\n",
    "            return min(res)\n",
    "        return dfs(0,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def f(s,e):\n",
    "            res = inf\n",
    "            for x in cuts:\n",
    "                if s < x < e:\n",
    "                    res = min(res, e - s + f(s, x) + f(x, e))\n",
    "            if res == inf:\n",
    "                return 0\n",
    "            return res\n",
    "        return f(0, n)\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        fcuts = [0]\n",
    "        fcuts.extend(cuts)\n",
    "        fcuts.append(n)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i + 1 == j:\n",
    "                return 0\n",
    "            if i + 2 == j:\n",
    "                return fcuts[j] - fcuts[i]\n",
    "            return min(dfs(i, m) + dfs(m, j) + fcuts[j] - fcuts[i] for m in range(i + 1, j))\n",
    "        \n",
    "        return dfs(0, len(fcuts) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts) -> int:\n",
    "        # 定义递归函数，i和j表示当前区间的左右端点\n",
    "        @cache\n",
    "        def dfs(i:int,j:int)->int:\n",
    "            # 边界条件：当区间长度小于等于1时，不需要再切割，返回0\n",
    "            if i+1>=j:\n",
    "                return 0\n",
    "            res = inf \n",
    "            # 枚举所有可能的切割点\n",
    "            for cut in cuts:\n",
    "                if i < cut < j:\n",
    "                    # 递归计算左右两个子区间的最小代价，并更新最小值\n",
    "                    res = min(res, dfs(i, cut) + dfs(cut, j) )\n",
    "            # 返回当前区间的最小代价，加上当前区间的长度\n",
    "            return res + j - i if res != inf else 0\n",
    "        # 调用递归函数，计算整个区间【0,n】的最小代价\n",
    "        return dfs(0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i + 1 >= j:\n",
    "        #         return 0\n",
    "        #     res = inf\n",
    "        #     for cut in cuts:\n",
    "        #         if i < cut < j:\n",
    "        #             res = min(res, dfs(i,cut) + dfs(cut,j) + j - i)\n",
    "        #     return res if res != inf else 0\n",
    "        # return dfs(0,n)\n",
    "\n",
    "        cuts = [0] + sorted(cuts) + [n]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i + 1 >= j:\n",
    "                return 0\n",
    "            res = inf \n",
    "            for k in range(i+1,j):\n",
    "                 res = min(res, dfs(i,k) + dfs(k,j) + cuts[j] - cuts[i])\n",
    "            return res\n",
    "        return dfs(0,len(cuts) - 1)\n",
    "\n",
    "        # f = [[0] * (n+1) for _ in range(n+1)]\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     for j in range(i+2,n+1):\n",
    "        #         res = inf\n",
    "        #         for cut in cuts:\n",
    "        #             if i < cut < j:\n",
    "        #                 res = min(res,f[i][cut] + f[cut][j] + j - i)\n",
    "        #         f[i][j] = res if res != inf else 0\n",
    "        # return f[0][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        d = [0] + cuts + [n]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(l,r):\n",
    "            if r == l + 1:\n",
    "                return 0\n",
    "            t = inf\n",
    "            for i in range(l+1,r):\n",
    "                t = min(t, dfs(l,i)+dfs(i,r))\n",
    "            return t + d[r] - d[l]\n",
    "        return dfs(0, len(d) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        m = len(cuts)\n",
    "        cuts.sort()\n",
    "        arr = [0] + cuts + [n]\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if l == r:\n",
    "                return arr[r + 1] - arr[l - 1]\n",
    "            ans = inf\n",
    "            for k in range(l, r + 1):\n",
    "                ans = min(ans, dfs(l, k - 1) + dfs(k + 1, r) + arr[r + 1] - arr[l - 1])\n",
    "            return ans\n",
    "        return dfs(1, m)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        m = len(cuts)\n",
    "        cuts.sort()\n",
    "        arr = [0] + cuts + [n]\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if l == r:\n",
    "                return arr[r + 1] - arr[l - 1]\n",
    "            ans = inf\n",
    "            for k in range(l, r + 1):\n",
    "                ans = min(ans, dfs(l, k - 1) + dfs(k + 1, r))\n",
    "            return ans + arr[r + 1] - arr[l - 1]\n",
    "        return dfs(1, m)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        m = len(cuts)\n",
    "        cuts.sort()\n",
    "        arr = [0] + cuts + [n]\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if l == r:\n",
    "                return arr[r + 1] - arr[l - 1]\n",
    "            ans = inf\n",
    "            for k in range(l, r + 1):\n",
    "                ans = min(ans, dfs(l, k - 1) + dfs(k + 1, r) + arr[r + 1] - arr[l - 1])\n",
    "            return ans\n",
    "        return dfs(1, m)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "\n",
    "        cuts = [0] + sorted(cuts) + [n]\n",
    "\n",
    "        @cache\n",
    "        def dfs(left: int, right: int) -> int:\n",
    "            if left + 1 == right:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for c in range(left + 1, right):\n",
    "                res = min(res, dfs(left, c) + dfs(c, right) + cuts[right] - cuts[left])\n",
    "            return res if res != inf else 0\n",
    "\n",
    "        return dfs(0, len(cuts) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        m = len(cuts)\n",
    "        cuts.sort()\n",
    "        cuts= [0] +cuts + [n]\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i,j+1):    \n",
    "                res = min(res,f(i,k-1) + f(k+1,j) + cuts[j+1]-cuts[i-1])\n",
    "            return res\n",
    "        return f(1,m)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for x in cuts:\n",
    "                if i < x < j:\n",
    "                    res = min(dfs(i, x) + dfs(x, j) + j - i, res)\n",
    "            if res == inf:\n",
    "                res = 0\n",
    "            # print(i, j, res)\n",
    "            return res\n",
    "        return dfs(0, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        @cache\n",
    "        def helper(i, j): # i,j之间去切，最小开销\n",
    "            if i+1==j: # 无需切割 \n",
    "                return 0\n",
    "            ans = inf\n",
    "            for k in cuts:\n",
    "                if i<k<j:\n",
    "                    ans = min(ans, helper(i, k)+helper(k, j)+j-i)\n",
    "            return ans if ans!=inf else 0\n",
    "        return helper(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @functools.cache\n",
    "        def dfs(i, j):\n",
    "            if i + 1 > j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for c in cuts:\n",
    "                if i < c < j:\n",
    "                    res = min(res, dfs(i, c) + dfs(c, j) + (j - i))\n",
    "            return res if res != inf else 0\n",
    "\n",
    "        return dfs(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.append(0)\n",
    "        cuts.append(n)\n",
    "        cuts.sort()\n",
    "\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l + 1 == r:\n",
    "                return 0\n",
    "            return min(dfs(l, i) + dfs(i, r) for i in range(l+1, r)) + cuts[r] - cuts[l]\n",
    "\n",
    "        return dfs(0, len(cuts)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i >= j-1:\n",
    "                return 0\n",
    "            cost = inf\n",
    "            for x in cuts:\n",
    "                if i<x<j:\n",
    "                    cost = min(cost,dfs(i,x) + dfs(x,j) + j-i) # 不需要记录路径则不需要pop\n",
    "            return cost if cost!=inf else 0\n",
    "        return dfs(0,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i + 1 >= j:\n",
    "                return 0\n",
    "            res = inf \n",
    "            for cut in cuts:\n",
    "                if i < cut < j:\n",
    "                    res = min(res, dfs(i, cut) + dfs(cut, j) + j - i)\n",
    "            return res if res != inf else 0\n",
    "        return dfs(0, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(left: int, right: int) -> int:\n",
    "            if left + 1 == right:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for c in cuts:\n",
    "                if left < c < right:\n",
    "                    res = min(res, dfs(left, c) + dfs(c, right) + right - left)\n",
    "            return res if res != inf else 0\n",
    "\n",
    "        return dfs(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\r\n",
    "        cuts.sort()\r\n",
    "        # 定义函数dfs(l, r): 表示将存在于区间[l, r]内的所有cuts中的元素完成切割\r\n",
    "        # 的最小花费，由于cuts所有元素均在[0, n]中，所以dfs(0, n)为最终答案\r\n",
    "        @cache\r\n",
    "        def dfs(l, r):\r\n",
    "            # 使用二分找到cuts中存在于区间[l, r]的元素范围\r\n",
    "            lo, hi = bisect_right(cuts, l), bisect_left(cuts, r)\r\n",
    "            # 若上下界相等则意味着区间[l, r]中不包含cuts中的任何元素\r\n",
    "            if lo == hi: return 0\r\n",
    "            # 计算本次花费\r\n",
    "            cost = r - l\r\n",
    "            # 枚举所有分割点，计算所有分割方案产生的花费，从中取得最小值即可\r\n",
    "            return cost + min(dfs(l, c) + dfs(c, r) for c in cuts[lo:hi])\r\n",
    "        return dfs(0, n)\r\n",
    "        \r\n",
    "    # \r\n",
    "    def minCost2(self, n: int, cuts: List[int]) -> int:\r\n",
    "        cuts.sort()\r\n",
    "        f = cache(lambda l, r: min((r - l + f(l, c) + f(c, r) for c in cuts[bisect_right(cuts, l):bisect_left(cuts, r)]), default = 0))\r\n",
    "        return f(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        @lru_cache(None)\n",
    "        def dfs(l,r):\n",
    "            left , right = bisect.bisect_right(cuts,l) , bisect.bisect_left(cuts,r)\n",
    "            if left == right:return 0\n",
    "            cost = r - l\n",
    "            return cost + min(dfs(l,k) + dfs(k,r) for k in cuts[left:right])\n",
    "\n",
    "        return dfs(0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        # 定义函数dp(l, r): 表示将存在于区间[l, r]内的所有cuts中的元素完成切割的最小花费，由于cuts所有元素均在[0, n]中，所以dfs(0, n)为最终答案\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            # 使用二分找到cuts中存在于区间[l, r]的元素范围\n",
    "            left, right = bisect_right(cuts, i), bisect_left(cuts, j)\n",
    "            # 若上下界相等则意味着区间[l, r]中不包含cuts中的任何元素\n",
    "            if left == right:\n",
    "                return 0\n",
    "            # 计算本次花费\n",
    "            cost = j - i\n",
    "            # 枚举所有分割点，计算所有分割方案产生的花费，从中取得最小值即可            \n",
    "            return cost + min(dp(i, cut) + dp(cut, j) for cut in cuts[left: right])\n",
    "        return dp(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, cuts: List[int]) -> int:\n",
    "        cuts.sort()\n",
    "        cuts = [0] + cuts + [n]\n",
    "        m = len(cuts)\n",
    "        dic = {}\n",
    "        def dfs(i,j):\n",
    "            if (i,j) in dic:\n",
    "                return dic[(i,j)]\n",
    "            if i+1==j:\n",
    "                return 0\n",
    "            elif i+2==j:\n",
    "                ans = cuts[j]-cuts[i]\n",
    "                dic[(i,j)] = ans\n",
    "                return ans\n",
    "            ans = 1e7\n",
    "            for k in range(i+1,j):\n",
    "                ans = min(ans,dfs(i,k)+dfs(k,j)+cuts[j]-cuts[i])\n",
    "            dic[(i,j)] = ans\n",
    "            return ans\n",
    "        return dfs(0,m-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
